#include <cv.h>
#include <vector>
#include <iostream>

using namespace std;
using namespace cv;

void printMerge(vector<vector <int> > v) {
    unsigned int i; 
    for (i = 0; i < v.size(); i++) {
        unsigned int j;
        for (j = 0; j < v.at(i).size(); j++)
            std::cout << v.at(i).at(j) << ", ";
        std::cout << std::endl;
    }

}

int holes(Mat *in) {
    vector<vector<Point> > contours;
    vector<Vec4i> hierarchy;

    Mat temp;
    in->convertTo(temp, CV_8UC1);

    findContours(temp, contours, hierarchy, CV_RETR_CCOMP, CV_CHAIN_APPROX_SIMPLE);

    unsigned int i;
    int nHoles = 0;

    for (i = 0; i < contours.size(); i++) {
        if (hierarchy[i][3] != -1)
            nHoles++;
    }

    return nHoles;
}

/*int connectedComponents(Mat in) {
    vector<vector<Point> > contours;
    vector<Vec4i> hierarchy;

    Mat temp;
    in.convertTo(temp, CV_8UC1);

    findContours(temp, contours, hierarchy, CV_RETR_CCOMP, CV_CHAIN_APPROX_SIMPLE);

    return contours.size();
}*/


int getNeighbour(Mat *in, int row, int col, int lr, int tb) {
    Size s = in->size();

    if ((col + lr) < 0 || (col + lr) > (s.width - 1))
        lr = 0;
    if ((row + tb) < 0 || (row + tb) > (s.height - 1))
        tb = 0;

    return in->at<unsigned short int>(row + tb, col + lr);
}

int connectedComponents(Mat *in) {
    Size s = in->size();
    Mat label(s.width, s.height, CV_16UC1, Scalar(1000));
    vector<vector<int> > merging;

    int curlabel = 0;
    unsigned short int smallestLabel;

    // iterate over columns, then rows
    for (int i = 0; i < s.height; i++) {
        for (int j = 0; j < s.width; j++) {
            smallestLabel = 1000;
            // if this element is 'on'
            if (in->at<float>(i, j) > 0.9) {
                int neighbourLabels[2];

                neighbourLabels[0] = getNeighbour(&label, i, j, -1, 0);
//                neighbourLabels[1] = getNeighbour(label, i, j, 1, 0);
                neighbourLabels[1] = getNeighbour(&label, i, j, 0, -1);
//                neighbourLabels[3] = getNeighbour(label, i, j, 0, 1);


                if (neighbourLabels[0] < smallestLabel)
                    smallestLabel = neighbourLabels[0];
                if (neighbourLabels[1] < smallestLabel)
                    smallestLabel = neighbourLabels[1];
/*                if (neighbourLabels[2] < smallestLabel)
                    smallestLabel = neighbourLabels[2];
                if (neighbourLabels[3] < smallestLabel)
                    smallestLabel = neighbourLabels[3];*/

                if (smallestLabel == 1000) {
                    smallestLabel = curlabel;
                    label.at<unsigned short int>(i, j) = curlabel;
                    merging.push_back(vector<int>());
                    curlabel++;
                } else {
                    label.at<unsigned short int>(i, j) = smallestLabel;
                }

                int k;
                for (k=0; k<2; k++) {
                    if (neighbourLabels[k] < 1000 && neighbourLabels[k] != smallestLabel) {
                        merging.at(smallestLabel).push_back(neighbourLabels[k]);
                    }
                }
            }
        }
    }

    /*for (i=0; i < merging.size(); i++) {
        std::sort(merging.at(i).begin(), merging.at(i).end());
        merging.at(i).erase(std::unique(merging.at(i).begin(), merging.at(i).end()), merging.at(i).end());
    }*/

/*    for (i=0; i < s.height; i++) {
        for (j=0; j < s.width; j++) {
            unsigned int k;
            for (k=0; k < merging.size(); k++) {
                if (std::find(merging.at(k).begin(), merging.at(k).end(), label.at<int>(i, j)) != merging.at(k).end()) {
                    label.at<int>(i, j) = k;
                    break;
                }
            }
        }
    }*/
    bool uniq[merging.size()];

    for (unsigned int i=0; i < merging.size(); i++) {
        uniq[i] = true;
    }

    for (unsigned int i=0; i < merging.size(); i++) {
        for (unsigned int j=0; j < merging.at(i).size(); j++) {
            uniq[merging.at(i).at(j)] = false;
        }
    }

    int count = 0;
    for (unsigned int i=0; i < merging.size(); i++) {
        if (uniq[i]) {
            count++;
        }
    }

    return count;

}
